package lc;

import java.util.LinkedList;
import java.util.Queue;

public class lc994 {
    public static void main(String[] args) {
        orangesRotting(new int[][]{{2,1,1},{1,1,0},{0,1,1}});
    }
    public static int orangesRotting(int[][] grid) {
        int cnt = 0;
        int res = 0;
        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(grid[i][j] == 2) queue.add(new int[]{i, j});
                else if(grid[i][j] == 1) cnt++;
            }
        }

        while(!queue.isEmpty()){
            int len = queue.size();
            res++;
            for(int k = 0; k < len; ++k){
                int[] arr = queue.poll();
                int i = arr[0], j = arr[1];
                if(i > 0 && grid[i - 1][j] == 1){
                    grid[i - 1][j] = 2;
                    queue.add(new int[]{i - 1, j});
                    cnt--;
                }
                if(i < m - 1 && grid[i + 1][j] == 1){
                    grid[i + 1][j] = 2;
                    queue.add(new int[]{i + 1, j});
                    cnt--;
                }
                if(j > 0 && grid[i][j - 1] == 1){
                    grid[i][j - 1] = 2;
                    queue.add(new int[]{i, j - 1});
                    cnt--;
                }
                if(j < n - 1 && grid[i][j + 1] == 1){
                    grid[i][j + 1] = 2;
                    queue.add(new int[]{i, j + 1});
                    cnt--;
                }
            }
        }
        return cnt == 0 ? res - 1 : -1;
    }
}
